# @Author: Eric Ito
# @Date: 1/28/2009
# @Name: Project Euler Problem 24

"""
A permutation is an ordered arrangement of objects. For example, 3124 is
one possible permutation of the digits 1, 2, 3 and 4. If all of the
permutations are listed numerically or alphabetically, we call it lexicographic
order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

012
021
102
120
201
210

What is the millionth lexicographic permutation of the
digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

0123456789
0123456798
0132456789
0213456789
0231456789
"""
L = "0123456789"

LISTS = []

def buildLists():
    for i in L:
        tmp = []
        for j in L:
            tmp.append(j)
        LISTS.append(tmp)

def reset(i):
    LISTS[i] = []
    for j in L:
        LISTS[i].append(j)

def remove(list,items):
    for item in items:
        list.remove(item)

def permute(st):
    buildLists()
    num = ""
    counter = 0
    for a in LISTS[0]:
        #LISTS[1].remove(a)
        remove(LISTS[1],(a))
        for b in LISTS[1]:
            remove(LISTS[2],(a,b))
            for c in LISTS[2]:
                remove(LISTS[3],(a,b,c))
                for d in LISTS[3]:
                    remove(LISTS[4],(a,b,c,d))
                    for e in LISTS[4]:
                        remove(LISTS[5],(a,b,c,d,e))
                        for f in LISTS[5]:
                            remove(LISTS[6],(a,b,c,d,e,f))
                            for g in LISTS[6]:
                                remove(LISTS[7],(a,b,c,d,e,f,g))
                                for h in LISTS[7]:
                                    remove(LISTS[8],(a,b,c,d,e,f,g,h))
                                    for i in LISTS[8]:
                                        remove(LISTS[9],(a,b,c,d,e,f,g,h,i))
                                        for j in LISTS[9]:
                                            num = a + b + c + d + e + f + g + h + i + j
                                            counter += 1
                                            #print num
                                            #print counter, num
                                            if counter == 1000000:
                                               print "The 1,000,000th permutation is",num
                                               return
                                        reset(9)
                                    reset(8)
                                reset(7)
                            reset(6)
                        reset(5)
                    reset(4)
                reset(3)
            reset(2)
        reset(1)
    print counter






def main():
    permute(L)

if __name__ == "__main__":
    main()